from collections import deque
from functools import cache
from math import gcd, inf
from typing import *

class Solution:
    def countBeautifulPairs(self, nums: List[int]) -> int:
        ans = 0
        for i in range(len(nums)):
            for j in range(i + 1,len(nums)):
                a = int(str(nums[i])[0])
                b = int(str(nums[j])[-1])
                if gcd(a,b) == 1:
                    ans +=1

        return ans

so = Solution()
print(so.countBeautifulPairs([31,25,72,79,74]))

import heapq

class Solution:
    def makeTheIntegerZero(self, num1: int, num2: int) -> int:
        ans = inf

        
        def f(num,id,k):
            if id > 60:
                return inf
            if num ==0:
                return 0
            ans = inf
            if k <2:
                ans = min(f(num - (1<<id) - num2,id,k+1) + 1,ans)
            ans = min(f(num,id+1,0),ans)
            return ans
        ans = f(num1,0,0)
        return -1 if ans == inf else ans
so = Solution()
# print(so.makeTheIntegerZero(num1 = 14, num2 = -18) == 1)
# print(so.makeTheIntegerZero(num1 = 3, num2 = -75) == 6)
# print(so.makeTheIntegerZero(num1 = 5, num2 = -21) == 3)
print(so.makeTheIntegerZero(num1 = 3, num2 = -2) == 3)
# print(so.makeTheIntegerZero(num1 = 5, num2 = 7) == -1)

# class Solution:
#     def numberOfGoodSubarraySplits(self, nums: List[int]) -> int:
#         n = len(nums)
#         f = [0] * n
#         last = -1
#         ans = 0
#         for i in range(n):
#             if nums[i] == 1:
#                 if last == -1:
#                     f[i] = 1
#                 else:
#                     f[i] = f[last] * (i - last)
#                 last = i
#             if f[i]!=0:
#                 ans = f[i]
#         return ans % 1000000007
    
# so = Solution()
# print(so.numberOfGoodSubarraySplits([0,1,0,0,1]))
# print(so.numberOfGoodSubarraySplits([0,1,0]))
